Матч 237, Путь по зеркалам (MirrorPath)

Дивизион 2, Уровень 3

Имеется карта лабиринта, в котором находятся зеркала. Стены обозначаются символом ‘#’, пустые места точкой ‘.’. Зеркала наклонены к линии основания под углом 45 градусов и обозначаются символом ‘/’ или ‘`’ (обратный слеш является специальным символом, поэтому здесь не используется). Лабиринт имеет всего два входа на периметре. Лазерный луч пускается в один из входов и выходит в другом. Зеркала расположены так, что пущенный луч в одном из входов всегда достигнет выхода.

Необходимо отобразить на карте ход лазерного луча, используя символы ‘-‘ (горизонтальное движение), ‘|’ (вертикальное движение), ‘+’ (лазер пересекает свой собственный путь).

Класс: MirrorPath

Метод: vector<string> path(vector<string> map)

Ограничения: Массив map содержит от 3 до 50 элементов ‘#’, ‘/’, ‘.’, ‘`’, элементы map имеют одинаковую длину от 3 до 50, в точности два символа на границе карты будут ‘.’, углы карты содержат ‘#’.

Вход. Карта map, описывающая состояние лабиринта.

Выход. Карта с отображением хода лазерного луча.

Пример входа

map

{"#.#",

"#.#",

"#.#"}

{"############",

"#######/....",

"######//####",

"#####//#####",

"####//######",

"..../#######",

"############"}

{"########.##",

"#./......`#",

"#../.`....#",

"#.`...../.#",

"#....`.../#",

"###.#######"}

Пример выхода

{"#|#",

"#|#",

"#|#"}

{"############",

"#######/....",

"######//####",

"#####//#####",

"####//######",

"..../#######",

"############"}

{"########|##",

"#./-----+`#",

"#.|/-`..||#",

"#.`+-+--/|#",

"#..|.`---/#",

"###|#######"}

РЕШЕНИЕ

моделирование

Проходим по границе лабиринта, ищем один из входов (не имеет значения какой). В координатах (x, y) храним текущее положение лазерного луча. В переменных dx и dy храним направление движения. Ось абсцисс направим вертикально, ординат – горизонтально. Таким образом, map[x][y] обозначает точку в x - ой строке и y - ом столбце. Если, например, найден вход на правой стенке карты, то устанавливаем dx = 0, dy = -1, так как от нее движение будет совершаться влево. Далее будем моделировать ход луча, то есть вместе с ним будем переходить от текущей клетки к следующей, добавляя к x и y соответственно dx и dy.

Пока луч не выйдет за границы карты (что возможно лишь тогда когда луч дойдет до выхода), смотрим на значение map[x][y]:

1. Если map[x][y] = ‘.’, то устанавливаем map[x][y] = ‘|’ или map[x][y] = ‘-’ в зависимости от того, идем мы по вертикальной или горизонтальной прямой. Движение происходит по горизонтали, если dx = 0.

2. Если map[x][y] = ‘/’ или map[x][y] = ‘`’, то следует повернуть на 90 градусов в соответствующем направлении. Для этого меняем значения переменных dx и dy между собой. В первом случае еще следует обратить значения этих переменных на противоположные.

3. Если map[x][y] равно другому какому-нибудь символу (‘-‘ или ‘|’), то ставим на этом месте ‘+’. Луч в этом случае пересекает сам себя.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <string>

using namespace std;

class MirrorPath

{

public:

vector<string> path(vector<string> map)

{

int i, x, y, dx, dy, n = map.size(), m = map[0].size();

for(x = y = dx = dy = i = 0; i < n; i++)

{

if (map[i][0] == '.') x = i, y = 0, dx = 0, dy = 1;

if (map[i][m-1] == '.') x = i, y = m - 1, dx = 0, dy = -1;

}

for(i = 0; i < m; i++)

{

if (map[0][i] == '.') x = 0, y = i, dx = 1, dy = 0;

if (map[n-1][i] == '.') x = n - 1, y = i, dx = -1, dy = 0;

}

while((x >= 0) && (x < n) && (y >= 0) && (y < m))

{

if (map[x][y] == '.')

{

if (dx) map[x][y] = '|'; else map[x][y] = '-';

} else

if (map[x][y] == '/')

{

swap(dx,dy);

dx = -dx; dy = -dy;

} else

if (map[x][y] == '`') swap(dx,dy);

else map[x][y] = '+';

x += dx; y += dy;

}

return map;

}

};